package main

/*
给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。

假定 BST 有如下定义：

结点左子树中所含结点的值小于等于当前结点的值
结点右子树中所含结点的值大于等于当前结点的值
左子树和右子树都是二叉搜索树

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-mode-in-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

import "leetcode/tree/common"

func findMode(root *common.TreeNode) []int {
	hashMap := make(map[int]int)
	var maxCnt int
	walk(root, hashMap, &maxCnt)
	var res []int
	for k, cnt := range hashMap {
		if cnt == maxCnt {
			res = append(res, k)
		}
	}
	return res
}

func walk(node *common.TreeNode, hashMap map[int]int, maxCnt *int) {
	if node == nil {
		return
	}
	cnt, exists := hashMap[node.Val]
	if !exists {
		hashMap[node.Val] = 0
	}
	hashMap[node.Val] = cnt + 1
	if (*maxCnt) < cnt+1 {
		(*maxCnt) = cnt + 1
	}
	walk(node.Left, hashMap, maxCnt)
	walk(node.Right, hashMap, maxCnt)
}

func main() {

}
